package Lee_code;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Deque;
import java.util.stream.Collectors;

/**
 * @author blh
 * @date 2024年08月16日 11:15
 */
public class Lee_435_816 {
    public int eraseOverlapIntervals(int[][] intervals) {
        int len = intervals.length;
        int count = 0;
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                // 只比较第一个元素
                if (o1[0] != o2[0]) {
                    return Integer.compare(o1[0], o2[0]);
                } else {
                    return Integer.compare(o1[1], o2[1]);
                }
            }
        });
        // 选择同开头最小的
        Deque<int[]> deque = new ArrayDeque<>();
        for (int i = 0; i < intervals.length; i++) {
            if (deque.isEmpty()) {
                // 如果为0添加元素
                deque.push(intervals[i]);
            } else {
                int[] pre = deque.peek();
                int[] cur = intervals[i];

                if (pre[1] >= cur[1]) {
                    deque.pop();
                    deque.push(cur);
                    count++;
                } else {
                    if (pre[1]<=cur[0]){
                        deque.push(cur);
                    } else {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}
